1. Technical Field of the Invention
The present invention generally relates to optical networks. More particularly, and not by way of any limitation, the present invention is directed to method and apparatus for dynamic provisioning of reliable connections in the presence of multiple failures in such networks.
2. Description of Related Art
Our society is increasingly dependent upon data networks. Survivability against network failure is therefore of paramount importance to guarantee uninterrupted availability of service. Many techniques exist for ensuring network survivability in the presence of a single failure; however, few, if any, techniques exist for ensuring a comparable level of survivability in the presence of multiple failures.
A significant amount of research in network survivability in high-speed optical networks has been carried out considering single component failures, such as the failure of a link or a node. Although the majority of transport requirements are well-served by providing resilience against single failures, there exists a need to provide similar resilience against multiple, especially double, failures. The rates of fiber cuts in some networks, as well as span maintenance operations, may create situations that are modeled as double and, more generally, multiple, failures. In addition, as optical networks comprise an increasingly higher number of network elements, the probability of having more than one of those elements fail during a short time interval is not negligible.
Furthermore, when a single failure, such as a link failure, occurs, recovery from the failure usually completes within a few tens of milliseconds. However, actual reparation of the physical link may take a few hours to a few days. During this time interval, the probability of a second link failure might not be unlikely, thus resulting in a non-negligible double-failure scenario probability.
“Survivability schemes” in Wavelength Division Multiplex (“WDM”) optical networks can be characterized in a variety of fashions. For example, such schemes may be “end-to-end” (i.e., path-based) or “local” (i.e., link-based); “centralized” or “distributed”; and “preplanned” (i.e., protection-oriented) or “dynamic” (i.e., restoration-oriented).
Dynamic survivability schemes (i.e., restoration-oriented schemes) , can easily accommodate the occurrence of multiple failures in a network; however, such schemes provide very slow switch-over from the failed path to the protection path. Path-based survivability schemes provide protection against multiple (m) failures by providing each connection with a working path and at least m protection paths. The problem with path-based schemes resides in the need to precompute end-to-end backup paths, while maximizing the sharing of protection resources. Greedy heuristic algorithms to calculate the amount of protection resources to overcome double failure scenarios are available, but not efficient or practical.
Link-based survivability schemes achieve protection by rerouting traffic along end nodes of a failed link. A number of schemes have been proposed which provide resiliency against double failures based on link protection. It is numerically demonstrable that providing readily-available resources against all possible double failures corresponds to a significant increase in the overall network cost; i.e., on the order of three times the cost of providing readily available resources against all single failures.
Another approach consists of providing resilience against any single failure in such a way that the maximum number of double failures is automatically protected against. With this approach, it is not possible to ensure reliability against all double failures for every connection demand; it is only possible to minimize the number of connections that are disrupted after the occurrence of a double failure.
Yet another approach is based on loop-back recovery. Different schemes that aim toward providing protection against double link failures are available. Other proposed schemes different in the amount of signaling required. There are also schemes that require the identification of failed links, knowledge of the order in which the failures occurred, and upon the second failure, memory of the first failure. Other schemes require only knowledge of the end nodes of the failed links irrespective of the sequence of the failures.
Path-based protection schemes suffer a high increase in the amount of resources that must be reserved, even when sharing of protection resources is efficiently utilized. The total amount of resources that have to be provisioned to provide resiliency to all connections against all double failures is nearly double the total amount of resources needed to provide resiliency to all connections against single failures. This cost increase is more pronounced when using dedicated path techniques.
Similar observations can be made with respect to link-based techniques. Additionally, while path-based techniques work at the Optical Channel layer in ITU G.872, link-based techniques are implemented at the Optical Multiplex Section (“OMS”) layer, making it more difficult to differentiate among the reliability requirements of various lightpaths.